package java;

import java.util.Arrays;

public class Question16 {
    public static void main(String[] args) {
        int[] nums = {-1,0,1,1,55};
        System.out.println(threeSumClosest(nums,3));
    }

    private static int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length < 3){
            return -1;
        }
        int res = nums[0] + nums[1] + nums[2];
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2 ; i ++){
            if (i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int oneRes = findThree(nums,i,target);
            if (Math.abs(oneRes - target) < Math.abs(res - target)){
                res = oneRes;
            }
        }
        return res;
    }

    private static int findThree(int[] nums, int index,int target) {
        int res = nums[index] + nums[index + 1] + nums[index + 2];
        int left = index + 1;
        int right = nums.length - 1;
        while (left < right){
            if (Math.abs(nums[right] + nums[left] + nums[index] - target) < Math.abs(res - target)){
                res = nums[right] + nums[left] + nums[index];
            }
            if (nums[left] + nums[right] + nums[index] < target){
                left ++;
            }else if (nums[left] + nums[right] + nums[index] > target){
                right --;
            }else {
                return res;
            }
            while (left < right && nums[left] == nums[left + 1]){
                left++; // 去重
            }
            while (left < right && nums[right] == nums[right - 1]){
                right--; // 去重
            }
        }
        return res;
    }
}
